package 链表;

import java.util.Arrays;

public class 两个链表的第一个公共结点 {


    public static void main(String[] args) {
        Node node = publicNode2();
        if (node != null){
            System.out.println(node.getValue());
        }else {
            System.out.println("没有找到公共节点");
        }
    }

    /**
     * 获取两个链表的长度，移动长度长的那个链表的指针，使两个链表的开始指针对齐
     * @return
     */
    public static Node publicNode2(){
        Node firstNode = NodeUtil.createNodeList(Arrays.asList(1,2,3,6,7));
        Node secondNode = NodeUtil.createNodeList(Arrays.asList(4,5,6,7));
        Node publicNode = null;
        int firstNodeLength = NodeUtil.length(firstNode);
        int secondNodeLength = NodeUtil.length(secondNode);
        int skip = 0;
        if (firstNodeLength > secondNodeLength){
            skip = firstNodeLength - secondNodeLength;
            //firstNode 指针往后移动skip 步
            while (skip != 0) {
                firstNode = firstNode.getTail();
                skip-- ;
            }

        }else{
            //secondNode 指针往后移动skip 步
            skip = secondNodeLength - firstNodeLength;
            while (skip != 0) {
                secondNode = secondNode.getTail();
                skip-- ;
            }
        }
        //开始指针对齐后一起往后移动
        while (secondNode != null && firstNode != null) {
           if (secondNode.getValue() == firstNode.getValue()){
                publicNode = secondNode;
                break;
           }
            secondNode = secondNode.getTail();
            firstNode = firstNode.getTail();
        }
        return publicNode;

    }
    public static Node publicNode(){

        Node firstNode = NodeUtil.createNodeList(Arrays.asList(1,2,3,6,7));
        Node secondNode = NodeUtil.createNodeList(Arrays.asList(4,5,5,8));

        Node firstPointer = firstNode;
        Node secondPointer = secondNode;

        Node publicNode = null;

        while(firstPointer != null ){

            while (secondPointer != null){
                if (firstPointer.getValue() == secondPointer.getValue()){
                    publicNode = firstPointer;
                    break;
                }
                secondPointer = secondPointer.getTail();
            }
            if (publicNode != null){
                break;
            }
            firstPointer = firstPointer.getTail();
            secondPointer = secondNode;
        }

        return publicNode;
    }

}
